// Copyright [2020] <unknown>
#include <bits/stdc++.h>
using namespace std;
// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define dbg(x...) { cerr << "\033[32;1m" << #x << " -> "; err(x); }
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif

#define sz(x) ((int)x.size())

typedef long long LL;

const int N = 1000;

int prime[N], pcnt, minp[N], pid[N];

int a[N], n;
void init() {
    for (int i=2; i<N; ++i) {
        if (!minp[i]) {
            minp[i] = i;
            pid[i] = pcnt;
            prime[pcnt++] = i;
        }
        for (int j=0; j<pcnt; ++j) {
            int nextp = i * prime[j];
            if (nextp >= N)
                break;
            if (!minp[nextp])
                minp[nextp] = prime[j];
            if (i % prime[j] == 0)
                break;
        }
    }
    // for (int i=0; i<10; ++i)
    //     dbg(i, prime[i]);
}


bool vis[N];

int ans[N];


int main(int argc, char const *argv[]) {
    // code
    init();
    int t;
    scanf("%d", &t);
    for (int kk=0; kk<t; ++kk) {
        scanf("%d", &n);
        memset(vis, 0, sizeof(bool) * n);
        for (int i=0; i<n; ++i) {
            scanf("%d", &a[i]);
            ans[i] = pid[minp[a[i]]];
        }
        vector<int> disc;
        for (int i=0; i<n; ++i) {
            disc.push_back(ans[i]);
        }
        sort(disc.begin(), disc.end());
        disc.resize(unique(disc.begin(), disc.end()) - disc.begin());
        for (int i=0; i<n; ++i) {
            ans[i] = lower_bound(disc.begin(), disc.end(), ans[i]) - disc.begin()+1;
        }
        printf("%d\n", sz(disc));
        for (int i=0; i<n; ++i)
            printf("%d%c", ans[i], i==n-1? '\n':' ');


    }
    return 0;
}
